package leetcode_day._2023._11;

/**
 * 689. 三个无重叠子数组的最大和
 * 算法: 滑动窗口、动态规划 + 前缀和
 *
 * @author yezh
 * @date 2023/11/19 14:47
 */
public class _19 {

    public int[] maxSumOfThreeSubarrays_slide_window(int[] nums, int k) {
        int[] ans = new int[3];
        int n = nums.length;
        int sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
        int sum2 = 0, maxSum12 = 0, maxSum12Idx1 = 0, maxSum12Idx2 = 0;
        int sum3 = 0, maxTotal = 0;
        for (int i = 2 * k; i < n; i++) {
            sum1 += nums[i - 2 * k];
            sum2 += nums[i - k];
            sum3 += nums[i];
            if (i >= 3 * k - 1) {
                if (sum1 > maxSum1) {
                    maxSum1 = sum1;
                    maxSum1Idx = i - 3 * k + 1;
                }
                if (maxSum1 + sum2 > maxSum12) {
                    maxSum12 = maxSum1 + sum2;
                    maxSum12Idx1 = maxSum1Idx;
                    maxSum12Idx2 = i - 2 * k + 1;
                }
                if (maxSum12 + sum3 > maxTotal) {
                    maxTotal = maxSum12 + sum3;
                    ans[0] = maxSum12Idx1;
                    ans[1] = maxSum12Idx2;
                    ans[2] = i - k + 1;
                }
                sum1 -= nums[i - 3 * k + 1];
                sum2 -= nums[i - 2 * k + 1];
                sum3 -= nums[i - k + 1];
            }
        }
        return ans;
    }

    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.length;
        reverse(nums);
        long[] sum = new long[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
        // f[i][j]: 前 i 个数中 j 个不重复子数组的最大和
        long[][] f = new long[n + 10][4];
        for (int i = k; i <= n; i++)
            for (int j = 1; j < 4; j++)
                f[i][j] = Math.max(f[i - 1][j], f[i - k][j - 1] + sum[i] - sum[i - k]);
        int[] ans = new int[3];
        // 看不懂
        int i = n, j = 3, idx = 0;
        while (j > 0) {
            if (f[i - 1][j] > f[i - k][j - 1] + sum[i] - sum[i - k]) --i;
            else {
                ans[idx++] = n - i;
                i -= k; j--;
            }
        }
        return ans;
    }

    void reverse(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int c = nums[l];
            nums[l++] = nums[r];
            nums[r--] = c;
        }
    }

}
